package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 2002. 两个回文子序列长度的最大乘积
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/6 16:40
 */
public class MaxProduct2 {

    public static void main(String[] args) {
        MaxProduct2 test = new MaxProduct2();

        // 9
//        String str = "leetcodecom";

        // 25
//        String str = "accbcaxxcxx";

        // 1
//        String str = "bb";

        // 36
        String str = "aaaaaaaaaaaa";

        int i = test.maxProduct(str);
        System.out.println(i);

    }

    private char[] arr;
    private int[] as;
    private int[] bs;
    private int al;
    private int bl;
    private int length;
    private int max;

    public int maxProduct(String s) {
        arr = s.toCharArray();
        length = s.length();
        as = new int[length];
        bs = new int[length];
        find(0);
        return max;
    }

    private void find(int index) {
        if (index == length) {
            if (al == 0 || al == length) {
                return;
            }
            int l = al >> 1;
            for (int i = 0; i < l; i++) {
                if (arr[as[i]] != arr[as[al - 1 - i]]) {
                    return;
                }
            }
            find();
            return;
        }
        as[al++] = index;
        find(index + 1);
        al--;
        bs[bl++] = index;
        find(index + 1);
        bl--;
    }

    private void find() {
        int[][] dp = new int[bl][bl];
        for (int i = 0; i < bl; i++) {
            dp[i][i] = 1;
        }
        for (int i = bl - 2; i >= 0; i--) {
            for (int j = i + 1; j < bl; j++) {
                if (arr[bs[i]] == arr[bs[j]]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        max = Math.max(max, dp[0][bl - 1] * al);
    }

}
